package sword_offer;

/**
 * @author Synhard
 * @version 1.0
 * @Class sword_offer.Code32
 * @Description 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。
 * 假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1}
 * 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-03-19 14:21
 */
public class Code32 {
    public static void main(String[] args) {
        int[] pushed = {1,2,3,4,5};
        int[] popped = {4,5,3,2,1};
        System.out.println(validateStackSequences(pushed, popped));
    }
    public static boolean validateStackSequences(int[] pushed, int[] popped) {
        TempStack<Integer> stack = new TempStack<>(pushed.length);
        int popIndex = 0;
        for (int j : pushed) {
            stack.push(j);
            while (stack.getLength() != 0 && stack.getTop() == popped[popIndex]) {
                stack.pop();
                popIndex++;
            }
        }
        return stack.getLength() == 0;
    }
}
/*
声明一个辅助栈
遍历pushed数组
依次入栈
当栈顶元素和popped数组对应位置元素相等时弹出栈
对应位置进行更新
若最后栈空则说明匹配成功
栈非空则说明匹配失败
 */